package com.study.bniarysearch;

import java.util.Arrays;

public class BinarySearchTest {

    public static void main(String[] args) {
//        int[] ints = getInts(10);
//
//        MergeSort mergeSort = new MergeSort();
//        ints = mergeSort.run(ints.clone());

        int[] ints = {1, 2, 3, 4, 5, 5, 8, 8, 8, 8, 9, 10, 11};
        int[] index = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        System.out.println(Arrays.toString(index));
        System.out.println(Arrays.toString(ints));

        int tag = 100;
//        int firstIndex = findFirst(ints, tag);
        int firstIndex = findFirst2(ints, ints.length, tag);
        System.out.println("\"" + tag + "\"的第一个出现的位置是:" + firstIndex);
//        int lastIndex = findLast(ints, tag);
        int lastIndex = findLast2(ints, tag);
        System.out.println("\"" + tag + "\"的最后一个出现的位置是:" + lastIndex);
//        int firstBiggerIndex = findFirstBigger(ints, tag);
        int firstBiggerIndex = findFirstBigger1(ints, tag);
        System.out.println("\"" + tag + "\"的第一个大于等于出现的位置是:" + firstBiggerIndex);
        int lastSmaller = findLastSmaller(ints, tag);
        System.out.println("\"" + tag + "\"的最后一个小于等于出现的位置是:" + lastSmaller);
        int lastSmaller1 = findLastSmaller1(ints, tag);
        System.out.println("\"" + tag + "\"的最后一个小于等于出现的位置是:" + lastSmaller1);

        System.out.println(rotatedSortedArray(new int[]{4, 5, 6, 7, 0, 1, 2}, 5));

    }

    /**
     * 二分法求给定值第一次出现的位置
     */
    private static int findFirst(int[] array, int tag) {
        int m = binarySearch(array, tag);

        if (m == -1) {
            return m;
        }
        while (array[m - 1] == tag) {
            m--;
        }
        return m;
    }


    public static int findFirst2(int[] a, int n, int value) {
        int l = 0;
        int h = n - 1;
        while (h > l) {
            int mid = (h + l) >> 1;
            if (a[mid] > value) {
                h = mid - 1;
            } else if (a[mid] < value) {
                l = mid + 1;
            } else {
                if (mid == 0 || a[mid - 1] < value) {
                    return mid;
                } else {
                    h = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 二分法求给定值最后一次出现的位置
     */
    private static int findLast(int[] array, int tag) {
        int m = binarySearch(array, tag);
        if (m == -1) {
            return m;
        }
        while (array[m + 1] == tag) {
            m++;
        }
        return m;
    }

    private static int findLast2(int[] array, int tag) {
        int l = 0, h = array.length - 1;
        while (h > l) {
            int m = (l + h) >> 1;
            if (array[m] > tag) {
                h = m - 1;
            } else if (array[m] < tag) {
                l = m + 1;
            } else {
                if (m == array.length - 1 || array[m + 1] > tag) {
                    return m;
                } else {
                    l = m + 1;
                }
            }
        }
        return -1;
    }

    private static int binarySearch(int[] array, int tag) {
        int l = 0;
        int h = array.length - 1;

        int m = 0;
        while (array[m] != tag && l < h) {
            if (array[m] > tag) {
                h = m - 1;
            } else {
                l = m + 1;
            }
            m = (l + h) / 2;
        }
        return array[m] == tag ? m : -1;
    }

    /**
     * 第一个大于等于给定值的位置
     */
    private static int findFirstBigger(int[] array, int tag) {
        int l = 0, h = array.length;
        int m = 0;

        while (array[m] != tag && l < h) {
            if (array[m] > tag) {
                h = m - 1;
            } else {
                l = m + 1;
            }
            m = (l + h) / 2;
        }

        while (m < array.length && (array[m - 1] >= tag || array[m] < tag)) {
            if (array[m - 1] >= tag) {
                m--;
            } else if (array[m] < tag) {
                m++;
            }
        }
        return m < array.length ? m : -1;
    }


    private static int findFirstBigger1(int[] array, int tag) {
        int l = 0, h = array.length - 1;
        while (h >= l) {
            int m = (l + h) >> 1;
            if (array[m] >= tag) {
                if (m <= 0 || m >= array.length - 1 || array[m - 1] < tag) {
                    return m;
                } else {
                    h = m - 1;
                }
            } else {
                l = m + 1;
            }
        }
        return -1;
    }

    /**
     * 最后一个小于等于给定值的位置
     */
    private static int findLastSmaller(int[] array, int tag) {
        int l = 0, h = array.length;
        int m = 0;


        while (l < h && array[m] != tag) {
            if (array[m] > tag) {
                h = m - 1;
            } else {
                l = m + 1;
            }
            m = (l + h) / 2;
        }


        if (m > array.length - 1) {
            return array.length - 1;
        }
        while (array[m + 1] <= tag || array[m] > tag) {
            if (array[m + 1] <= tag) {
                m++;
            } else if (array[m] > tag) {
                m--;
            }
            if (m + 1 < 0 || m + 1 > array.length - 1) {
                return -1;
            }
        }
        return m;
    }

    private static int findLastSmaller1(int[] array, int tag) {
        int l = 0, h = array.length - 1;
        while (h >= l) {
            int m = (l + h) >> 1;
            if (array[m] > tag) {
                h = m - 1;
            } else {
                if (m <= 0 || m >= array.length - 1 || array[m + 1] > tag) {
                    return m;

                } else {
                    l = m + 1;
                }
            }
        }
        return -1;
    }

    private static int rotatedSortedArray(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }

        int len = nums.length;

        int offset = 0;
        while (offset < nums.length - 1 && nums[offset] < nums[offset + 1]) {
            offset++;
        }
        if (offset > nums.length) {
            offset = -1;
        }
        offset++;

        int l = 0;
        int h = len - 1;
        while (l < h) {
            int m = l + ((h - l) >> 1);
            int rM = (m + offset) % len;
            if (nums[rM] > target) {
                h = m - 1;
            } else if (nums[rM] < target) {
                l = m + 1;
            } else {
                return rM;
            }
        }

        int r = (l + offset) % len;
        return nums[r] == target ? r : -1;
    }

}
